package midsearch;

import java.util.Random;

/**
 * 题目 ：按照权重，来生成随机数
 * 题目详述 ：
 * 给定一个正整数数组w ，其中w[i]代表下标 i的权重（下标从 0 开始），
 * 请写一个函数pickIndex，它可以随机地获取下标 i，选取下标 i的概率与w[i]成正比。
 *
 * 例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3)= 0.25 （即，25%），
 * 而选取下标 1 的概率为 3 / (1 + 3)= 0.75（即，75%）。
 * 也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
 */
public class PickIndex {
    /**
     * 核心思想 ：
     * （1）int[] w，整型数组中所存储的是，数组下标的权重；
     * （某个数组下标权重 = 当前数组权重值 / 数组总权重值）
     * （2）使用累加权重数组sums，来存储前i个权重数组元素之和；
     * （累加权重数组sums的大小和权重数组w 是一样的，同时累加权重数组中第i个数组元素都对应着 权重数组中前i个数组元素之和）
     * （3）由于题目需要按照权重来生成随机数，即 ===》 生成的随机数p :[0 , 数组总权重值）；
     *  使用累加权重数组中 [第i-1累加权重值,第i个累加权重值），来指向数组下标 i；
     *  （即，使用 大于等于前一个累加权重值 && 小于当前累加权重值 的随机数来表示下标i，来实现按照权重，来生成随机数）
     * （4）随机生成一个随机数p，需要去寻找其所对应的下标；
     * （即，通过累加权重数组，由于累加权重数组是顺序的，同时累加权重数组中 [第i-1累加权重值,第i个累加权重值），是来指向数组下标 i）
     * 可以通过二分查找，快速定位该随机数所对应的下标；
     * a.若是该随机数 >= sums[middle]的话，即说明在累加权重数组的后半部分；
     * b.若是该随机数 < sums[middle]的话，即说明在累加权重数组的前半部分；
     */
    // 累加权重数组（用于判断生成的随机数指向的是哪个下标）
    int[] sums;
    // 用于记录权重数组中的总权重值发
    int total;
    // sums累加权重数组的初始化
    public PickIndex(int[] w) {
        // 若是不给total变量赋予初始值的话，那么系统会给其默认赋值 0
        total = 0;
        sums = new int[w.length];
        // 初始化累加权重数组
        for(int i = 0 ; i < w.length; i++){
            total += w[i];
            sums[i] = total;
        }
    }
    // 按照权重进行生成随机数（也就是下标）
    public int pickIndex() {
        Random random = new Random();
        // 所生成的随机数，取值范围为[0 , total)
        int p = random.nextInt(total);
        return findIndex(p);
    }
    // 使用二分查找，去查询第一个大于随机数p的下标
    public int findIndex(int p){
        int start = 0;
        int end = sums.length - 1;
        while(start <= end){
            int middle = (start + end) / 2;
            // 即，所需要的结果在 累加权重数组的前半部分；
            if(sums[middle] > p){
                // 此处逻辑，也就是用来判断当前下标是否是第一个大于随机数p的下标；
                // 同时满足随机数p，是在[前一个数组元素，当前遍历数组元素)；
                // 等价于，前一个数组元素 <= 随机数p < 当前正在遍历的数组元素
                // 特殊情况：middle == 0，即说明了当前正在遍历的数组元素不存在前一个元素；
                if(middle == 0 || sums[middle - 1] <= p){
                    return middle;
                }
                end = middle - 1;
            }
            // 即，所需要的结果在 累加权重数组的后半部分；
            else {
                start = middle + 1;
            }
        }
        // 由于随机数p的取值范围[0,total)，即按照道理来说，累加权重数组中必然会有某数组元素大于随机数p
        return -1;
    }
    /**
     * 分析 ：
     * 题目要求 ：根据每个下标的权重，随机地生成每个下标；
     * （1）即，累加所有权重，得到总权重值，使得随机数的生成范围[0,总权重值)，同时使用该范围内某些数字来，来表示一个下标
     * ===》 通过控制随机数生成范围内，某个下标所对应的数字范围来实现 根据权重来生成随机下标；
     * （2）如何将所生成的随机数p转化成其对应的下标？
     * ===> 新创建一个累加权重数组，其中的每个元素都存储着 前面所有下标对应的权重值之和；
     *  随机数p 对应 某个下标i 的情况 ：
     *  即，随机数p 在[下标i-1所对应的累加权重值,下标i所对应的累加权重值) 范围内的话，即代表随机数p 对应的下标是 i；
     *
     *
     *  findIndex方法的时间复杂度: 由于使用了二分查找，即时间复杂度O（logn）（其中，n为累加权重数组中的元素数目）
     *  需要注意的是 ：权重数组与累加权重数组中所存储的元素个数是一样的，即两个数组的大小是一致的；
     */
}
